package com.wujunshen.algorithm.leetcode.backtracking;

import java.util.HashSet;
import java.util.Set;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/30 21:49<br>
 */
public class N皇后II {
    public int totalNQueens(int n) {
        String[][] board = new String[n][n];

        Set<Integer> col = new HashSet<>();
        Set<Integer> posDaig = new HashSet<>();
        Set<Integer> negDiag = new HashSet<>();

        return backTracking(0, n, board, col, posDaig, negDiag);
    }

    public int backTracking(int row, int n, String[][] board, Set<Integer> col, Set<Integer> posDaig,
                            Set<Integer> negDiag) {
        if (row == n) {
            return 1;
        }

        int count = 0;
        for (int c = 0; c < n; c++) {
            if (col.contains(c) || posDaig.contains(row + c) || negDiag.contains(row - c)) {
                board[row][c] = ".";
                continue;
            }

            board[row][c] = "Q";
            col.add(c);
            posDaig.add(row + c);
            negDiag.add(row - c);

            count += backTracking(row + 1, n, board, col, posDaig, negDiag);

            board[row][c] = ".";
            col.remove(c);
            posDaig.remove(row + c);
            negDiag.remove(row - c);
        }
        return count;
    }
}
